---
title: "排队打水"
created: 2025-11-28
tags:
  - 算法
---

# 排队打水

## 题目 [排队打水](https://www.acwing.com/problem/content/description/915/)

![[image-231cb819.png]]

## 思路分析

大概算是个短作业优先的问题

直觉上的做法就是 需要时间少的先做呗

用优先队列，因为放入队列时会自动把最小的放到队列最前面，越往后数越大。

如果第一个人去接水，后面的人都要等待他的节水时间，所以res要加上：第一个人的节水时间\*后面的人数。（代码中为x \* t）

证明一下正确性：

![[image-650856f3.png]]

## 代码实现

优先队列：

```cpp
#include<bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>,greater<int>> heap;

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        int x;cin>>x;

        heap.push(x);

    }

    long long res=0;

    int later=n-1;

    while(later){

        int time=heap.top();

        heap.pop();

        res+=later*time;

        later--;

    }

    cout<<res;

    return 0;

}
```

前缀和

```cpp
//假如现在轮到第i个人打水，那么他的等待时间为所有在他前面打水的人的打水时间之和，所以可以排序后记录前缀和，最后用for循环累加答案.

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;

int a[N];

long long w[N];

int main()

{

    cin >> n;

    for(int i = 1;i <= n;i++)

        cin >> a[i];

    sort(a+1, a+1+n);

    for(int i = 1;i <= n;i++)

        w[i] = w[i-1]+a[i];

    long long res = 0;

    for(int i = 1;i < n;i++)

        res += w[i];

    cout << res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[排序 权贪心（短作业优先 重权值优先）|排序 权贪心（短作业优先 重权值优先）]] 🏠 [[00-刷题理模型]] ➡️ [[最小消耗|最小消耗]]